// Sort.cs

using System;
using System.Collections;
using System.Collections.Generic;

namespace Mono.Algorithm
{
	/// <summary>
	/// Specifies a sort order 
	/// </summary>
	public enum SortOrder
	{
		Ascending,
		Descending,
	}
	
	public partial class Algorithm
	{
		/// <summary>
		/// Provides a delegate type for sorting methods
		/// </summary>
		/// <typeparam name="T">Type of elements in the sequence (N.B. The type must implement IComparable)</typeparam>
		/// <param name="a">The object to compare against</param>
		/// <param name="b">The object to compare with</param>
		private delegate bool SortMethod<T>(T a, T b) where T : IComparable<T>;

		/// <summary>
		/// Provides a comparison check for sorting in an ascending order
		/// </summary>
		/// <typeparam name="T">Type of elements in the sequence (N.B. The type must implement IComparable)</typeparam>
		/// <param name="a">The object to compare against</param>
		/// <param name="b">The object to compare with</param>
		private static bool SortAscending<T>(T a, T b) where T : IComparable<T>
		{
			return a.CompareTo(b) < 0;
		}

		/// <summary>
		/// Provides a comparison check for sorting in a descending order
		/// </summary>
		/// <typeparam name="T">Type of elements in the sequence (N.B. The type must implement IComparable)</typeparam>
		/// <param name="a">The object to compare against</param>
		/// <param name="b">The object to compare with</param>
		private static bool SortDescending<T>(T a, T b) where T : IComparable<T>
		{
			return a.CompareTo(b) > 0;
		}

		/// <summary>
		/// Sorts a given sequence in an ascending order
		/// </summary>
		/// <typeparam name="T">Type of elements in the sequence (N.B. The type must implement IComparable)</typeparam>
		/// <param name="seq">The sequence to sort</param>
		/// <param name="start">The index to sort from</param>
		/// <param name="end">The index to sort to</param>
		/// <param name="sortOrder">Indicates the order to use for sorting</param>
		public static List<T> Sort<T>(List<T> seq, int start, int end, SortOrder sortOrder) where T : IComparable<T>
		{
			// Validate the arguments
			// 
			// If the sequence has a count of less than 1 or is null then we cannot sort it
			if (seq == null || seq.Count <= 1)
			{
				throw new ArgumentException("A valid sequence must be provided");
			}

			// If the starting index is greater than the number of items in the list, is less then zero
			// then throw an error
			if (start < 0 || start >= seq.Count)
			{
				throw new IndexOutOfRangeException("The start index is out of range");
			}

			// If the end index is less than zero or greater than the number of items in the sequence then throw
			// an error
			if (end < 0 || end >= seq.Count)
			{
				throw new IndexOutOfRangeException("The end index is out of range");
			}

			// Default the sorting method to ascending
			SortMethod<T> sortMethod = SortAscending<T>;

			// If the user has specified a descending order then switch to the descending method
			if (sortOrder ==  SortOrder.Descending)
			{
				sortMethod = SortDescending<T>;
			}

			// Iterate over each index in the subset of the sequence specified
			for (int nextIndex = start; nextIndex <= end; nextIndex++)
			{
				// Set the replacement index to the current index position
				int replacementIndex = nextIndex;

				// Check each subsequent index position
				for (int checkIndex = nextIndex; checkIndex <= end; checkIndex++)
				{
					// If the index being checked is valid according to the sorting method then set the replacement
					// index to the current index being checked
					if (sortMethod(seq[checkIndex], seq[replacementIndex]) == true)
					{
						replacementIndex = checkIndex;
					}
				}

				// If the replacement index is different from the current index then swap the values at the two positions
				if (replacementIndex != nextIndex)
				{
					T holder = seq[nextIndex];
					seq[nextIndex] = seq[replacementIndex];
					seq[replacementIndex] = holder;
				}
			}

			// Return the ordered sequence
			return seq;
		}

		/// <summary>
		/// Sorts a given sequence in an ascending order
		/// </summary>
		/// <typeparam name="T">Type of elements in the sequence (N.B. The type must implement IComparable)</typeparam>
		/// <param name="seq">The sequence to sort</param>
		/// <param name="start">The index to sort from</param>
		/// <param name="end">The index to sort to</param>
		/// <param name="sortOrder">Indicates the order to use for sorting</param>
		public static T[] Sort<T>(T[] seq, int start, int end, SortOrder sortOrder) where T : IComparable<T>
		{
			return Sort<T>(new List<T>(seq), start, end, sortOrder).ToArray();
		}
	}
}
